#include "my_link.h"

list_inf H = NULL;

void Reverse_to(list_inf l) // 逆序
{
    node *temp = NULL;
    node *p = l->head->next;

    while (NULL != p)
    {
        temp = p->prev;
        p->prev = p->next;
        p->next = temp;
        p = p->next;
    }
    temp = l->head;
    l->head = l->end;
    l->end = temp;
}

void link_sort(list_inf l, int (*cmp)(const void *, const void *)) // 使用cmp效率降低
{

    node *link_head = l->head->next;

    node *temp = NULL;
    node *max_l = NULL;

    node *link_end = l->end;
    if (NULL == l->head->next)
    {
        return;
    }

    while (link_head != link_end)
    {
        temp = link_head;
        max_l = link_head;

        while (link_end != temp)
        {
            if (1 == cmp(max_l->data, temp->data)) // max_l->data > temp->data)
                max_l = temp;

            temp = temp->next;
        }

        if (max_l == link_head)
        {
            link_head = link_head->next;
        }

        max_l->prev->next = max_l->next;
        if (NULL != max_l->next)
        {
            max_l->next->prev = max_l->prev;
        }

        // temp = l->end;
        max_l->next = l->end->next; // 尾节点链信息赋值给最大值节点
        max_l->prev = l->end;       // 最大值节点的上一节点为end

        l->end->next = max_l; // 更新尾节点
        l->end = max_l;       //
    }

    temp = l->head->next;
    max_l = l->head->next->next;

    while (NULL != max_l && (-1 == cmp(max_l->data, temp->data))) // max_l->data < temp->data))
    {
        max_l = max_l->next;
    }

    temp->prev->next = temp->next; // 链表删节点
    temp->next->prev = temp->prev;

    temp->next = max_l; // 赋值
    if (NULL != max_l)
    {
        temp->prev = max_l->prev;
        max_l->prev->next = temp; // 插入
        max_l->prev = temp;
        return;
    }
    l->end->next = temp;
    temp->prev = l->end;
    l->end = temp;
    return;
}

long int link_len(list_inf l)
{
    return l->size;
}

list_inf link_create(void)
{
    list_inf l = (list_inf)malloc(sizeof(struct _list));
    node *n = (node *)malloc(sizeof(node));

    if (NULL == n || NULL == l)
    {
        fprintf(stderr, "to_link_create:: malloc error\n");
        exit(1);
    }

    n->next = NULL;
    n->prev = NULL;

    l->head = l->end = n;
    l->size = 0;

    return l;
}

// 摧毁这个链表
void link_destory(list_inf l)
{
    node *p = l->head->next, *q;
    l->head->next = NULL;
    while (p != NULL)
    {
        q = p->next;
        free(p->data);
        free(p);
        p = q;
    }

    l->end = l->head;
    l->size = 0;
    free(l->head);
    free(l);
}

// 清除链表释放出了头节点以外的所有节点
void link_clear(list_inf l)
{
    node *p = l->head->next, *q;
    l->head->next = NULL;
    while (p != NULL)
    {
        q = p->next;
        free(p->data);
        free(p);
        p = q;
    }

    l->end = l->head;
    l->size = 0;
}

// 向链表插入新节点

// 尾插
void link_push_back(list_inf l, data_type *data)
{
    // 创建一个新的节点
    node *n = (node *)malloc(sizeof(node));
    if (NULL == n || NULL == l)
    {
        fprintf(stderr, "link_push_back:: malloc error\n");
        return; // exit(1);
    }

    n->data = data;
    n->next = NULL;
    n->prev = l->end;
    // 新节点加入链表

    l->end->next = n;
    l->end = n;
    l->size++;
}

// 头插
void link_push_front(list_inf l, data_type *data)
{
    // 创建一个新节点
    node *n = (node *)malloc(sizeof(node));
    if (NULL == n || NULL == l)
    {
        fprintf(stderr, "link_push_front:: malloc error\n");
        return; // exit(1);
    }

    n->data = data;
    n->next = l->head->next;
    n->prev = l->head->prev;

    // 新节点加入链表
    l->head->prev = n;
    l->head->next = n;

    if (NULL == n->next)
        l->end = n;

    l->size++;
}

// 中插

void link_insert(list_inf l, unsigned poe, data_type *data)
{
    node *n = (node *)malloc(sizeof(node));
    node *p = NULL;
    if (NULL == n || NULL == l)
    {
        fprintf(stderr, "link_insert:: malloc error\n");
        return; // exit(1);
    }

    n->data = data;

    // 新节点加入链表
    p = l->head;

    while (p->next != NULL && poe--)
        p = p->next;

    n->next = p->next;
    n->prev = p;
    p->next = n;

    if (NULL == n->next)
        l->end = n;
    else
        n->next->prev = n;

    l->size++;
}

// 删除某个节点 cmp函数 找到返回 0 未找到返回 1
void link_remove(list_inf l, void *data, int (*cmp)(const void *, const void *))
{
    node *p = l->head->next;

    // 遍历链表找到要删除的节点
    while (p->next != NULL && cmp(data, &(p->data)))
    {
        p = p->next;
    }

    if (1 == cmp(data, &p->data))
    {
        return;
    }

    p->prev->next = p->next;

    if (NULL != p->next)
    {
        p->next->prev = p->prev;
    }
    else
    {
        l->end = p->prev;
    }

    l->size--;
    // 如果删除了尾节点，将p改为尾节点
    free(p);
}

// 修改链表里某个界节点的数据
int link_updata(list_inf l, data_type *data, data_type *new_data, int (*cmp)(const void *, const void *))
{
    node *p = l->head->next;

    while (p->next != NULL && cmp(data, p->next->data))
        p = p->next;

    if (NULL == p->next)
        return 0;

    p->data = new_data;
    return 1;
}

// 在链表中查找某个数据，如果找到了就返回数据指针，否则返回NULL cmp函数返回 非0 是相等，返回 0 是不同
data_type *link_find(list_inf l, data_type *data, int (*cmp)(const void *, const void *))
{
    node *p = l->head->next;

    while (p != NULL && cmp(data, p->data))
        p = p->next;

    if (p == NULL)
        return NULL;

    return (p->data);
}

// 在链表中查找某个数据，如果找到了就返回链表指针
node *find_link_struct(list_inf l, void *data, int (*cmp)(const void *, const void *))
{
    node *temp = l->head;

    while (temp->next != NULL && cmp(temp, data))
        temp = temp->next;
    if (temp->next == NULL)
        return NULL;

    return temp;
}
